Resource arbitration is a fundamental problem in computer and telecommunications network design. An arbiter controls the access of a plurality of competing inputs to a desired resource such as a bus or multiplexer in a computer or telecommunications network.
In particular, high speed arbitration among inputs with variable priorities is needed to support variable priority communications in a dynamic multi-tasking environment and to accommodate the increasing speed of highly pipelined data parallel buses and high speed statistical multiplexers. Preferably, the arbiter carries out a round-robin scheduling process to insure that all inputs of equal priority achieve fair access to the resource being arbitrated.
A variety of arbiters have been disclosed in the prior art. However, as is discussed below, only a few of the prior art arbiters support variable priority arbitration. One prior art arbiter is disclosed in Bogdan Lent, "A Variable Arbiter for Resource Allocation in Asynchronous Multiprocessor Systems," Microprocessing and Microprogramming, Vol. 9, 1982. This arbiter is based on a priority comparison matrix and can support variable priority arbitration or a first-come, first-served scheduling policy. However, this arbiter does not support round-robin scheduling on variable priority classes and, in addition, it has a space complexity of order N.sup.2, where N is the number of inputs. Thus, this arbiter increases in size too rapidly with large N.
An arbiter with a round-robin scheduling policy and with a policy for handling urgent requests is disclosed in Mary K. Vernon et al, "Distributed Round-Robin and First-come, First-serve Protocols and Their Application to Multiprocessor Bus Arbitration," The ACM 15th Annual International Symposium on Computer Architecture, 1988 and in D. M. Taub, "Arbitration and Control Acquisition Scheme for the IEEE 896 Futurebus," IEEE Micro, Vol. 4, No. 4, August 1984, pp. 28-41. However, these arbiters do not support round-robin arbitration for multiple priority classes.
To match the speed of highly pipelined buses and multiplexers, an arbiter with a round-robin scheduling policy and with a sublinear time complexity is desired. The linear array based round-robin arbiters proposed in Joseph K. Muppala et al, "Arbiter Designs for Multiprocessor Interconnection Networks," Microprocessing and Microprogramming, Vol. 26, 1989 and in G. Cioffi et al, "A Fully Distributed Arbiter for Multi-processor Systems," Microprocessor and Microprogramming, Vol. 11, pp. 15-22, 1983, have O(N) time complexity. Since the arbitration time of these arbiters increases linearly with the number of input ports, they cannot match the data transfer rate in a highly pipelined communications system where N is large.
In the case of highly parallel and pipelined bus systems, arbitration needs to be performed in each system clock cycle. Arbitration schemes that utilize a table lookup method to implement rotating priority arbitration (see. e.g., A. B. Kovaleski, "High-Speed Bus Arbiter for Multiprocessor," IEE Proc. Vol. 130, Pr, E, No. 2, March 1983 and the Vernon et al reference identified above) can reach higher speeds but their space complexity will increase exponentially with the number of inputs and the number of priority classes.
Distributed arbiters (see, e.g., the Taub, Cioffi et al, and Vernon et al references identified above) have the advantage of modularity. However, their arbitration time is relatively long compared to that of a centralized arbiter. In order to support P priority levels and N input nodes, the arbitration process needs to step through log.sup.P priority bus lines and log.sup.N node identification bus lines to reach a distributed arbitration decision. Although the distributed arbitration scheme only requires on the order of (log.sup.P +log.sup.N) time steps, each step requires a long delay due to off-chip communications, bus propagation, wire or glitch elimination, and capacitive loads of bus drivers.
Briefly stated, none of the above-identified prior art arbiters is entirely satisfactory for use in high speed computer and telecommunications networks because they are incapable of handling multiple priority classes, because they do not utilize a round-robin scheduling policy, because the time or space complexity is too great, or because centralized arbitration is not utilized.
In view of the foregoing, it is an object of the present invention to provide an arbiter and associated arbitration process which overcomes the shortcomings of the above-described prior art arbiters. It is a further object of the invention to provide an arbiter and associated arbitration process suitable for use in high speed computer and communications systems.
More particularly, it is an object of the invention to provide an arbiter and associated arbitration process whose arbitration speed increases sublinearly as the number N of inputs increases. It is also an object of the invention to provide an arbiter and associated arbitration process which implements a round-robin scheduling policy, which is capable of handling multiple priority classes and which is centralized.